这道题应该算是 的前置知识了吧。可惜之前我并没有做过。
对于一棵以 为根的子树,它的重心只可能在点 或 以点 的重儿子为根的子树中。
那么类比 倍增父亲,树的重心倍增重儿子。
An Ac a day, keeps the doctor away!
这道题应该算是 CSP2019 树的重心 的前置知识了吧。可惜之前我并没有做过。
对于一棵以 u 为根的子树,它的重心只可能在点 u 或 以点 u 的重儿子为根的子树中。
那么类比 lca 倍增父亲,树的重心倍增重儿子。
n 个点 m 条边的无向无环图,其实就是一个森林。
题目要求最小化两个量:灯数和只被一边照亮的边数。
一个做法是定义两个 dp 数组,分别表示最小灯数和在灯数最小情况下的一边被照亮的最小边数。
首先有个想法,如果该位为 0 且不是前导 0,则将 0 的数量加一,最后看 0 是否出现了至少 ⌈2len⌉ 次。
但这样有个问题,比如在 n=8(1000)2 时, 2(0010) 就不会被计入答案 ,原因是 2 的前导 0 也算在了它二进制的位数中。
所以还要记录前导零的数量 leadnum,最后判断是否出现至少 ⌈2len−leadnum⌉ 即可。
每个数的数字和的和其实就是所有数字与它出现次数的积的和。
那么对于 0−9 ,依次像 P2602 [ZJOI2010]数字计数 统计出现次数就可以了。
具体做法也很简单,记录前 pos 位某个数字出现次数 sum,记忆化搜索即可通过。
设整数 n 的 lqp 拆分权值为 g(n) , 那么有:
i=1∑nj=i+1∑nlcm(Ai,Aj)